#include <stdio.h>
#include <string.h>
#include "BigInt.h"






BigInt complement(BigInt& x){
	int i;
	BigInt sub;	//substraction
	
	for( i = max256 - 1; i >= 0; i-- )	//	complement_255
		sub.digit[i] = 255 - x.digit[i];

	
	for( i = max256 - 1; i >= 0; i-- ){	//	complement_256 = complement_255 + 1
		sub.digit[i] = sub.digit[i] + 1;
		if( sub.digit[i] == 0 )
			continue;				//	if overfloat, continue plus 1 to the next digit
		else
			break;						//	if not, stop the operation
	}
	return sub;
}

BigInt minimulti(BigInt &number, unsigned char &digit, int &index){
	BigInt rslt;	//	result
	unsigned int temp;		//	temp is int in order to control the overfloating
	unsigned char overfloat;
	int i, j;

	for( i = 0; i <= max256 - 1; i++ )
		rslt.digit[i] = 0;		//	set rslt = 0
	
	overfloat = 0;
	i = max256 - 1;			//	multiply variable number by digit from right to left
	j = index;			//	store result from index (also store from right to left)
	while( j >= 0 ){	//	if j < 0, rslt is overfloat. So just stop multipling at this point, no matter wheather varable number has not been multplied by all digits yet
		unsigned char ab = (int)digit;
		temp = (int) digit * (int)number.digit[i] +  overfloat;
		if( temp > 255 )					//	check if temp is overfloat (int 256 base)
			overfloat = temp/255;			//	temp has been overflown. Then carry a value = overfloat value / base to next digit
		else
			overfloat = 0;
		rslt.digit[j] = (unsigned char)temp;	
		j--;	i--;
	}
	return rslt;
}

int compare(BigInt &x, BigInt &y){
	int i;
	for( i = 0; i <= max256 - 1; i++ ){
		if( x.digit[i] > y.digit[i] )
			return 1;
		if( x.digit[i] < y.digit[i] )
			return -1;
		if( x.digit[i] == y.digit[i] )
			continue;
	}return 0;
}




BigInt plus(BigInt& x, BigInt& y){
	BigInt sum;
	int i;
	unsigned char overfloat;
	overfloat = 0;

	for( i = max256 - 1; i >= 0; i-- ){
		sum.digit[i] = x.digit[i] + y.digit[i] + overfloat;
		if( (sum.digit[i] > x.digit[i]) || (sum.digit[i] > y.digit[i]) || (sum.digit[i] == 0 && x.digit[i] == 0 && y.digit[i] == 0) )	//	check if sum.digit[i] does not overflow
			overfloat = 0;		 
		else
			overfloat = 1;			//	in plus operation, the carried value (if exists) is always 1
	}
	return sum;
}

BigInt minus(BigInt& x, BigInt y){
	y = complement(y);
	return plus(x, y);
}

BigInt multi(BigInt &x, BigInt &y){
	BigInt rslt;		//	result
	BigInt temp[max256];
	int i, j, k, choice;

	for( i = 0; i <= max256 - 1; i++ )
		rslt.digit[i] = 0;				//	set	rslt = 0
	
	j = 0; k = 0;
	for( i = 0; i <= max256; i++ ){		//	skip the digtits 0. They don't affect the multiply operation
		if( x.digit[i] == 0 )			//	j is the number of digit 0 of x
			j++;
		if( y.digit[i] == 0 )			//	i is the number of digit 0 of y
			k++;
	}
	if( j < k )				//	choose the BigInt number which has less non-0 digts  ->
		choice = 0;			//	-> Use the digits of this number to multiply by the other BigInt number, the fonction 'minmulti' will be called less time
	else
		choice = 1;
	
	switch(choice){
	case 0:
		k = 0;		//	k reprsents for index of temp
		for( i = max256 - 1; i >= j; i-- ){
			temp[k] = minimulti(y, x.digit[i], i);
			rslt = plus(rslt, temp[k]);		//	rslt += temp[k]
			k++;
		}return rslt;
	case 1:
		j = 0;		//	j reprsents for index of temp
		for( i = max256 - 1; i >= k; i-- ){
			temp[j] = minimulti(x, y.digit[i], i);
			rslt = plus(rslt, temp[j]);		//	rslt += temp[j]
			j++;
		}return rslt;
	}
}

int div(BigInt &quotient, BigInt x, BigInt& y){
	int i;

	i = 0;
	while( i <= max256 - 1){			//	check if y = 0;
		if( y.digit[i] != 0 )
			break;
		++i;
	}if( i == max256 )
		return 0;
	BigInt B1;

	B1.digit[max256 - 1] = 1;
	for( i = 0; i <= max256 - 2; ++i )	//	set B1 = 1
		B1.digit[i] = 0;

	for( i = 0; i <= max256 - 1; ++i )
		quotient.digit[i] = 0;			//	set quotient = 0
	while( !(compare(x, y) == -1) ){	//	loop when x > y
		quotient = plus(quotient, B1);
		x = minus(x, y);				//	quotient ++
	}return 1;
}

int mod(BigInt &modulo, BigInt &x, BigInt &y){
	BigInt quotient;

	if( !( div(quotient, x, y) ) )
		return 0;
	modulo = minus( x, multi(y, quotient) );	// x mod y = x - (x div y)
	return 1;
}
	



BigInt and(BigInt &x, BigInt &y){
	BigInt rslt;		//	result
	int i;
	for( i = 0; i <= max256 - 1; i++ )
		rslt.digit[i] = x.digit[i] & y.digit[i];
	return rslt;
}

BigInt or(BigInt &x, BigInt &y){
	BigInt rslt;		//	result
	int i;
	for( i = 0; i <= max256 - 1; i++ )
		rslt.digit[i] = x.digit[i] | y.digit[i];
	return rslt;
}

BigInt xor(BigInt &x, BigInt &y){
	BigInt rslt;		//	result
	int i;
	for( i = 0; i <= max256 - 1; i++ )
		rslt.digit[i] = x.digit[i] ^ y.digit[i];
	return rslt;
}

void not(BigInt &x){
	int mask;
	int i;
	
	mask = -1;	// -1 = 1111 1111.... 1111
	for( i = 0; i <= max256 - 1; i++ )
		x.digit[i] = x.digit[i] ^ (-1);
}

void sfl( BigInt &x, int n ){
	unsigned char mask1, mask2;
	unsigned char temp;		//	variable temp stores the MSB of each byte to carry to next byte
	int i, j;
	mask1 = 1;			//	0000 0001
	mask2 = mask1 << 7;	//	1000 0000
	
	for( j = 0; j <= n - 1; j++ ){					//	shift left n times, each time 1 bit
		temp = x.digit[max256 - 1] & mask2;			//	indentify the MSB of this byte
		x.digit[max256 - 1] <<= 1;					//	process the last byte first, cause it is not affected by the others
		for( i = max256 - 2; i >= 0; i-- ){			//	shift all byte, from right to left
			x.digit[i] <<= 1;						//	shift left one digit
			if( temp )								//	if MSB of digit[i-1] is 1, then temp != 0 (true)
				x.digit[i] = x.digit[i] | mask1;	//	carry bit 1 of the digit[i-1] to digit[i]
			temp = x.digit[i] & mask2;				//	store MSB of x.digit[i] to temp
		}
	}
}
	
void sfr( BigInt &x, int n ){
	unsigned char mask1, mask2;
	unsigned char temp1, temp2;		//	variable temp stores the LSB of each byte to carry to next byte
	int i, j;
	mask1 = 1;				//	0000 0001
	mask2 = mask1 << 7;		//	1000 0000
	for( j = 0; j <= n - 1; j++ ){					//	shift right n times, each time 1 bit
		temp1 = x.digit[0] & mask1;					//	indentify the MSB of this byte
		x.digit[0] >>= 1;							//	process the first byte first, cause it is not affected by the others
		for( i = 1; i <= max256 - 1; i++ ){			//	shift all byte, from left to right
			temp2 = x.digit[i] & mask1;				//	store LSB of x.digit[i] to temp
			x.digit[i] >>= 1;						//	shift left one digit
			if( temp1 )								//	if LSB of digit[i-1] is 1, then temp != 0 (true)
				x.digit[i] = x.digit[i] | mask2;	//	carry bit 1 of the digit[i-1] to digit[i]
			temp1 = temp2;
		}
	}
}
